// LeetCode 主站 Problem Nr. 1290: 二进制链表转整数

/*
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。
已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：
	输入：head = [1,0,1]
	输出：5
	解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
	输入：head = [0]
	输出：0
示例 3：
	输入：head = [1]
	输出：1
示例 4：
	输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
	输出：18880
示例 5：
	输入：head = [0,0]
	输出：0
提示：
    链表不为空。
    链表的结点总数不超过 30。
    每个结点的值不是 0 就是 1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"
	"math"

	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func getDecimalValue(head *ListNode) int {
    return method2(head)
}

func convert(head *ListNode) *ListNode {
	var previous *ListNode
	current := head
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}
	return previous
}

func method1(head *ListNode) int {
	head = convert(head)
	result := 0
	index := 0.0
	current := head

	for current != nil {
		if current.Val != 0 {
			result += int(math.Pow(2, index))
		}

		index += 1.0
		current = current.Next
	}

	return result
}

func method2(head *ListNode) int {
	result := 0
	for current := head; current != nil; current = current.Next {
		result = result * 2 + current.Val
	}
	return result
}

func main() {
	head := ds.BuildSinglyLinkedList([]int{1,0,0,0,0})
	fmt.Println(getDecimalValue(head))
}
